1.將N個數(shù)據(jù)按照從小到大順序組織存放在一個單向鏈表中。如果采用二分查找，那么查找的平均時間復(fù)雜度是O(logN)。
F

? ? 解析：
? ? 二分查找的平均復(fù)雜度是O（logN）沒有錯，一看到這個就跳坑了。然后知道陷阱來了！按順序存放在單項鏈表中。二分查找是不可以用鏈表存儲的：
? ? 這是由鏈表的特性決定的。鏈表是很典型的順序存取結(jié)構(gòu)，數(shù)據(jù)在鏈表中的位置只能通過從頭到尾的順序檢索得到，即使是有序的，要操作其中的某個數(shù)據(jù)也必須從頭開始。
? ? 這和數(shù)組有本質(zhì)的不同。數(shù)組中的元素是通過下標(biāo)來確定的，只要你知道了下標(biāo)，就可以直接存儲整個元素，比如a[5],是直接的。鏈表沒有這個，所以，折半查找只能在數(shù)組上進(jìn)行。

? ? 在單鏈表中，要訪問某個結(jié)點，只要知道該結(jié)點的指針即可。因此，單鏈表是一種隨機(jī)存取結(jié)構(gòu)。
? ? F

? ? 解析：
? ? 線性表分(順序存儲和鏈?zhǔn)酱鎯?
? ? 順序存儲即數(shù)組,我們使用數(shù)組的時候申請的是連續(xù)的內(nèi)存空間可以直接讀取的，a[24],a[25]
? ? 鏈?zhǔn)酱鎯存湵恚湵碇袉蝹€節(jié)點的內(nèi)存地址不是連續(xù)的，而是散列在計算機(jī)中，通過next指針訪問下一個節(jié)點，所以所必須遍歷鏈表才能讀取數(shù)據(jù)！
? ? 總結(jié):
? ? 順序表:順序存儲，隨機(jī)讀取
? ? 鏈?zhǔn)?隨機(jī)存儲,順序讀取(必須遍歷)

? ? 取線性表的第i個元素的時間同i的大小有關(guān)。
? ? F

? ? 解析：
? ? 線性表分順序表和鏈表
? ? 順序表最主要的特點是隨機(jī)訪問，即通過首地址和元素序號可以在O(1)的時間內(nèi)找到指定的元素
? ? 線性表因為是按序號直接取值，所以沒有關(guān)系，但如果是鏈?zhǔn)酱鎯Y(jié)構(gòu)就有關(guān)系

4.在具有頭結(jié)點的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指向鏈表中的第一個元素結(jié)點。F

? ? 解析：
? ? 頭指針 指示鏈表中第一個結(jié)點（即第一個數(shù)據(jù)元素的存儲映像）的存儲位置。同時，由于最后一個數(shù)據(jù)元素沒有直接后繼，則線性鏈表中最后一個結(jié)點的指針為“空”（NULL）。
? ? 有時在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱之為頭結(jié)點 。 頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲如線性表長度等類的附加信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針（即第一個元素結(jié)點的存儲位置）。單鏈表的頭指針指向頭結(jié)點。若線性表為空，則頭結(jié)點的指針域為“空”。

有頭結(jié)點的鏈表結(jié)構(gòu)中，頭指針指向鏈表的頭結(jié)點，因為單鏈表不具有回溯性，即通過指針指向的節(jié)點不能找到該節(jié)點的前一個節(jié)點，只能找到后面的節(jié)點。

目的是便于鏈表的操作；比如刪除第一個數(shù)據(jù)節(jié)點時，讓頭結(jié)點的指針域指向第二個數(shù)據(jù)節(jié)點即可。如果頭指針指向的是第一個數(shù)據(jù)節(jié)點，那么通過此指針不能找到前一個節(jié)點，也就不能實現(xiàn)刪除。

5.在一個設(shè)有頭指針和尾指針的單鏈表中,執(zhí)行刪除該單鏈表中最后一個元素的操作與鏈表的長度無關(guān)F

? ? 解析：
? ? 必須要遍歷到倒數(shù)第二個元素把它設(shè)為尾部（鏈表不是雙向鏈表）

6.在用數(shù)組表示的循環(huán)隊列中，front值一定小于等于rear值。F

? ? 解析：
? ? rear在對max取余之后會從零開始，但這時front并不是零。所以會出現(xiàn)front>rear,（ >,=,<三種情況都有可能出現(xiàn)）
? ? （可以這樣理解：因為是循環(huán)的，所以可能rear由大變小，畫個圖就知道了。）

7.若采用“隊首指針和隊尾指針的值相等”作為環(huán)形隊列為空的標(biāo)志，則在設(shè)置一個空隊時只需將隊首指針和隊尾指針賦同一個值，不管什么值都可以。T

? ? 解析：
? ? 判斷隊滿的方式一：犧牲一個存儲的單元來區(qū)分空隊、滿隊

約定：當(dāng)隊頭指針在隊尾指針的下一個位置時，隊滿
隊空：q.frontq.rear
隊滿：(q.rear+1)%MAXSIZEq.front
隊列中的元素個數(shù)：(q.rear-q.front+MAXSIZE)%MAXSIZE

在這里插入圖片描述

? ? 答案：T
? ? 解析：注意題目中的字眼：“任一指定序號”“最后”，說明已經(jīng)確定了位置，此時根據(jù)時間復(fù)雜度，順序線性表的查找為 O(1) ,因為實在最后進(jìn)行插入和刪除的，所以不涉及元素的移動，（如果插入和刪除的位置不在最后，則刪除過后刪除位置之后的元素要全部往前移，插入時要先將插入位置之后的元素全部往后移來騰出空間插入，所以這是插入和刪除操作的時間復(fù)雜度就為 O(n) ）。 如果時線性鏈表，則每次取相應(yīng)的元素時都要進(jìn)行遍歷，此時的時間復(fù)雜度為 O(n) 。插入和刪除如果指明位置時時間復(fù)雜度為 O(1) ,如果沒有指明位置則仍需要先遍歷找到位置再操作，此時的時間復(fù)雜度為 O(n) 。